/**
 * 
 */
package interval.passed;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * @author xyyi
 *
 */
public class MergeIntervals {

	/**
	Given a collection of intervals, merge all overlapping intervals.

	For example,
	Given [1,3],[2,6],[8,10],[15,18],
	return [1,6],[8,10],[15,18].
	 */
	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
		// Start typing your Java solution below
		// DO NOT write main() function
		ArrayList<Interval> result = new ArrayList<Interval>();
		if (intervals == null || intervals.isEmpty())
			return result;

		Collections.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				if (o1.start < o2.start)
					return -1;
				if (o1.start > o2.start)
					return 1;
				return 0;
			}
		});

		int start = intervals.get(0).start;
		int end = intervals.get(0).end;
		for (int i = 1; i < intervals.size(); i++) {
			if (end < intervals.get(i).start) {
				result.add(new Interval(start, end));
				start = intervals.get(i).start;
				end = intervals.get(i).end;
			} else {
				end = Math.max(intervals.get(i).end, end);
			}
		}

		result.add(new Interval(start, end));
		return result;
	}

	/**
	 * Definition for an interval.
	 */
	public class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	/**
	 * 
	 */
	public MergeIntervals() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
